1. Field of the Invention
The present invention relates generally to computer graphics, and more particularly to the generation of planar maps of three-dimensional surfaces.
2. Related Art
The problem of flattening a three dimensional (3-D) surface into a two-dimensional (2-D) domain is age old and takes several forms.
For example, one of the central concerns of cartography is the representation of a sphere as a planar map. As is well known, it is impossible to represent such a surface in 2-D without distortion and discontinuity. In a Mercator projection, for example, Greenland appears much larger than it really is in relation to more southern countries. Cartographers mitigate this problem either by cutting the surface of the globe into segments, thus trading off increased discontinuity for decreased distortion, or by using other projections which trade off size distortions for shape distortions.
Other application areas involve surface flattening, or the inverse problem, the construction of 3-D surfaces from originally flat components. An example of flattening involves taking the hide of an animal and creating flat pieces of leather or fur. An example of the inverse process is the construction of apparel such as shoes and garments out of pieces of leather, fur, or cloth. Going in either direction involves stretching/shrinking (distortion) and the alteration of discontinuity/continuity (e.g., by cutting or sewing).
The problem of correspondences between flat and curved surfaces arises in computer graphics software. A technique known as texture mapping is used to give 3-D surfaces character and realism. Whenever there exists a mapping from a 3-D surface to a 2-D region, an arbitrary image can be identified with the 2-D region so that rendered attributes of the surface (e.g., color, shininess, displacement) are controlled by the image's values. An image used in this way is called a texture map.
For 3-D surfaces such as bicubic patches, the mapping from surface to a 2-D region is intrinsic. However, for 3-D surfaces composed of polygons, an a priori mapping does not exist. The construction of such mappings, known as parameterization, has been a problem in computer graphics for several years because without a parameterization a polygonal surface is not amenable to texture mapping. Parameterization is equivalent to flattening.
Some conventional parameterization methods involve 1) selecting a boundary on a 3-D surface, 2) mapping the boundary to a planar convex polygon, and 3) using relaxation methods to calculate a mapping of interior points of the surface to interior points of the convex polygon. To visualize this process, imagine the 3-D surface to be a rubber sheet whose boundary is stretched around the perimeter of the polygon.
A drawback with these methods is that the planar convex polygon (e.g., a circle or square) does not necessarily reflect the shape of the surface boundary, thus increasing the possibility that the mapping will introduce shape distortions, particularly in polygons close to the boundary. A need therefore exists for an improved system and method for creating a planar boundary which inherits the geometry of a given surface boundary.